The present invention is directed to communications networking and in particular to networks that employ label switching.
Internetwork communications are based on operations of routers, which are network devices that determine, on the basis of destination information in packets that they receive, where to forward the packets so that they are likely to reach the intended destinations.
Routers vary widely, but FIG. 1 depicts a typical configuration. Router 10 includes a plurality of communications interfaces 12, 14, and 16. The interfaces 12. 14, and 16 include output and reception circuitry that respectively sends and receives signals to and from remote locations. The signals sent and received represent communications packets. When one of the interface modules receives an incoming packet, it sends the packet's header information over an internal communications bus 18 to a forwarding engine 20, typically a high-performance processor and associated storage circuitry, that determines where the packet should be sent and which interface to use for that purpose. The selected interface then transmits to a remote location an output packet formed from the input packet by packet-assembly circuitry implemented in one or more of the FIG. 1 modules.
A local-area-network bus such as FIG. 2's bus 22 may provide the medium by which router 10's selected interface communicates with the remote location. If so, the signals may be received not only by the intended recipient but also by other devices that the bus interconnects. So that devices like network nodes 24, 26, 28, and 30 can ignore packets not intended for them, the router may use, for instance, the Ethernet packet format, which FIG. 3 depicts.
Such a packet begins with a link-layer header 32 that includes, among other fields. one that contains a link-layer destination address. If the destination address does not match the link-layer address of a network-device interface that receives the packet, that network device ignores the packet.
For present purposes, we will assume that router 10 intends the packet to be received by a further router 24, so the link-layer header's destination-address field will contain the link-layer address of router 24's interface with network link 22. That interface accordingly reads the remainder of the packet, verifying that the contents of a cyclic-redundancy-code trailer 34 are consistent with the remainder of the packet. It then proceeds to process the link-layer packet's payload 36 in accordance with a protocol that the link-layer header's type field specifies.
In the present case, the type field specifies that the link-layer packet's payload is an Internet Protocol ("IP") datagram, a network-layer protocol data unit. The purpose of the router's IP process is to determine how to forward the datagram to its ultimate (inter-network-host) destination. To make this determination, the IP process inspects the IP datagram's header 38, and in particular its IP destination-address field. That field's contents identify the host system to which the datagram's contents are to be directed, and router 24 uses this address to determine through which of its interfaces to forward the packet on toward its ultimate destination.
The router makes this determination by using a forwarding table, into which it has distilled information about internetwork topology that it has obtained in various ways, but typically by communications with other routers. Routers inform other routers of the host systems to which they can forward communications packets, and they employ such information obtained from other routers to populate their forwarding tables.
Now, the IP address is 32 bits long in most versions and even longer in versions that will soon be adopted, so the IP address could theoretically distinguish among over four billion host systems. Actually, the number of host systems that have globally unique IP addresses is much smaller that this, but the number still is much greater than it is practical for an individual router to have route entries for in its forwarding table.
The solution to this problem historically has been to base the table look-up on destination-address prefixes. That is, some routers will simply indicate that they can handle traffic to all hosts whose destination addresses begin with a particular, say, 16-bit sequence, or "prefix." Additionally, a router may compact its information so as to store routes in this form. Prefixes vary in length, the longest being the most specific and thus presumably representing the best routes to the included host addresses. So when a router receives an IP datagram, it searches through the prefix entries in the forwarding table to find the longest prefix that matches the incoming packet's destination address. When it finds that route in its forwarding table, it reads that route's fields that specify the interface over which it should forward the packet and the link-layer address of the router to which the interface should send the packet for further forwarding.
Although this approach has proved quite serviceable and robust, it has exhibited shortcomings that have led some workers to propose a table-index-based forwarding approach for high-speed networks such as those of some Internet-service providers ("ISPs"). Specifically, routers would inform their neighbor routers of the locations within their tables at which the routes to particular prefixes are located. When their neighbors send them packets destined for those prefixes, they insert a "shim" between the link-layer header (such as an Ethernet header) and the network-layer header (typically, an IP header). This shim's contents include a label that is an index to the desired route in the receiving router's forwarding table.
One of this approach's advantages is that it relieves the receiving router of the need to perform an expensive longest-match search: the label directs the receiving router directly to the correct forwarding-table entry. More important, it affords ISPs the opportunity to have their ingress routers (which receive packets from outside the service-provider network) specify the egress routers through which received packets should issue from the provider network. This frees the ISP's interior ("transit") routers of the task of participating in forwarding policy and maintaining the associated information bases. Commonly assigned co-pending U.S. patent application Ser. No. 08/997,343, filed on Dec. 23, 1997, by Rekhter et al. for Peer-Model Support for Virtual Private Networks with Potentially Overlapping Addresses, describes in detail one proposal, known as Multiple-Protocol Label Switching ("MPLS"). for employing such shims. I hereby incorporate that application in its entirety by reference.
FIGS. 4 and 5 illustrate how such an operation can be performed. A customer router CE2 forwards a packet to an ingress router PE2 in an ISP network. The link-layer packet's payload consists of a datagram, including the datagram's payload data and a header that gives the destination's address as D1. The ISP needs to perform its routing rapidly, so it employs the label switching just described.
Router PE2 is an "edge" router: it has direct links with routers outside the service-provider network. The ISP's edge routers maintain communications with others of its edge routers, such as edge router PE1, to tell them the address prefixes of hosts outside the network to which they can forward packets. Because of this communication, router PE2 has in its forwarding database an indication that packets having a prefix that matches address D1 should be sent to PE1 for forwarding outside the service-provider network. When router PE2 receives the D1-destined packet from customer router CE2, it finds this information in its database through a conventional longest-match search. The entry that it thereby finds additionally indicates that PE1 has asked ingress edge routers such as PE2 to insert into such packets a shim-header stack entry bearing a label L3. That label is router PE1's forwarding-table index to information for forwarding packets to destination D1.
Since PE1 is not PE2's immediate neighbor, PE2 additionally looked up forwarding information for PE1 when it installed the route to the D1-including prefix into its forwarding table, and it found that packets destined for PE1 should be sent to neighbor router P2 for forwarding. We assume that it had additionally received from P2 a request that packets sent to router P2 for forwarding to router PE1 should be labeled with label L2. So router PE2 includes shim-header stack entries bearing labels L2 and L3 in a shim header that it prepends to the incoming packet's datagram. It encapsulates the result in a link-layer header and trailer.
As FIG. 5's second row illustrates, each stack entry includes a label field itself as well as three further fields. One is a class-of service ("COS") field, which router PE2 has copied from the IP header's corresponding field depicted in FIG. 3's second now. Routers may use this field's contents in allocating resources among competing data flows. Also copied from that header are the contents of a TTL ("Time To Live") field. Each router decrements this field before forwarding the packet. If the value reaches zero, the router discards the packet without forwarding it and may send a "TTL expired" message to the packet's source. The COS and TTL fields are separated by an end-of-stack ("S") field, consisting of one bit that indicates whether the stack entry is the bottom entry in the stack of which the shim header consists. As FIG. 5 illustrates, that field's value is zero in the case of the first, "top" label and one in the case of the second, "bottom" label.
Since router PE2 received a packet containing no shim header and has added one, it performed the operation of shim-header imposition. Another label-handling operation that it can perform is label replacement. Suppose that the ISP to which edge router PE2 belongs communicates not only with its customers but also with other ISPs and that router PE2 has a direct link to an edge router PE3 in such a neighbor ISP. Suppose further that router PE2 has arranged for router PE3 to label D1-destined packets with label L4 when it sends them to router PE2. So the D1-destined packet that PE2 receives from CE3 has that label in its shim header. PE2 can therefore avoid the longest-match search: it can fetch the needed forwarding information from the entry that the label specifies directly. In this case, the information indicates that label L4, which points to router CE2's entry for D1's prefix, should be replaced with label L3, which points to router CE1's entry for that prefix.
In addition to this replacement operation, router PE2 additionally performs a stack-push operation. Again, since router CE1 is not router CE2's direct neighbor. CE2 must include a label that directs its immediate neighbor router PE1 to router PE1's forwarding-table entry for CE1-destined packets. This label must be "pushed" onto the previously single-label stack in which the replacement occurred, with the result that the labels in the D1-destined packets that router CE2 forwards to transit router P2 in response to such packets from router PE3 are the same as those that it forwards it in response to such packets from router CE2.
The next router, router P2, illustrates label replacement only. Router P2 rapidly finds forwarding information for the received packet because the top entry in the shim header's entry stack contains the label L2 that identifies destination PE1 's correct entry in router P2's forwarding table. Among that table entry's information is the value of the label that the next router P1 has asked to be placed on packets sent to it for forwarding to PE1. It accordingly replaces the current top stack entry, namely, the one containing label L2, with one containing the label, L1, whose use router P1 has requested.
Router P1 in turn performs yet another label-forwarding procedure, a stack-pop operation. Whereas egress edge router PE1 has requested of ingress edge routers such as router PE2 that they place label L3 on packets sent to it for forwarding to D1, it has informed its immediate upstream neighbors such as router P1 that they should "pop" the label stack on packets forwarded to router PE1 for forwarding to destination D1. This places at the top of the shim header's stack the entry containing label L3, which is the index into router PE1's forwarding-table entry for D1-destined packets.
Guided by the forwarding information to which it is thereby directed, egress router PE1 forwards the packet to a further customer router CE1. In doing so, it performs a final type of label-forwarding operation, namely, shim-header removal. Customer router CE1 does not employ label switching, so the router CE1 forwards the packet without any label information.
An ISP employing this technique may wish to hide aspects of its internal topology. and to this end it may impose selective policies for propagation of time-to-live counts. Among the fields of the conventional IP header is the time-to-live ("TTL") field 40 in FIG. 3. This field is used to prevent endless looping by packets that fail to find their destination hosts. Each router normally decrements this field before forwarding the packet. If the value reaches zero, the router discards the packet without forwarding it and may send a "TTL expired" management-protocol message to the packet's source. As FIG. 5 shows, the ISP may use a similar shim-header field 42, propagating the TTL information from the IP header's TTL field into the shim header's TTL field when a packet first enters the provider network and propagating it back again when the packet leaves that network.
Such TTL-information propagation reveals the network's internal topology: any resultant "TTL expired" message identifies the IP address of the router where the packet expired. Although the ISP could disable such messages' generation, doing so in general is usually undesirable because it necessitates reconfiguring all the network's routers whenever it becomes necessary to perform internal route-tracing, operations, and such operations could not be enabled selectively at chosen provider-system entry points.
So it is desirable to allow routers to implement system policy regarding such information's propagation. If the policy is fixed and uniform, this poses no problem. An ISP's policy could simply be to forward packets internally without propagating the IP-header TTL information into the shim header. But policy implementation should normally be more flexible: the ISP should be able to make the decision depend on the packet's destination, for instance. Unfortunately, introducing such a dependency can add to routing delay.